package com.zjw.algorithm;

import com.zjw.algorithm.utils.Utils;


/**
 * 980. 不同路径 III
 * 困难
 * 290
 * 相关企业
 * 在二维网格 grid 上，有 4 种类型的方格：
 * <p>
 * 1 表示起始方格。且只有一个起始方格。
 * 2 表示结束方格，且只有一个结束方格。
 * 0 表示我们可以走过的空方格。
 * -1 表示我们无法跨越的障碍。
 * 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
 * <p>
 * 每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
 * 输出：2
 * 解释：我们有以下两条路径：
 * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
 * 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
 * 示例 2：
 * <p>
 * 输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
 * 输出：4
 * 解释：我们有以下四条路径：
 * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
 * 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
 * 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
 * 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
 * 示例 3：
 * <p>
 * 输入：[[0,1],[2,0]]
 * 输出：0
 * 解释：
 * 没有一条路能完全穿过每一个空的方格一次。
 * 请注意，起始和结束方格可以位于网格中的任意位置。
 */
public class Solution17 {

    public static void main(String[] args) {
        System.out.println(new Solution17().uniquePathsIII(Utils.createTwoDimensionArrayFromOneDimension(new int[]{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, -1}, 4)));
        System.out.println(new Solution17().uniquePathsIII(Utils.createTwoDimensionArrayFromOneDimension(new int[]{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2}, 4)));
    }

    private int count = 0;

    private int total = 0;

    private int width;

    private int height;

    public int uniquePathsIII(int[][] grid) {

        int box = 0;
        int x = 0;
        int y = 0;
        height = grid.length;
        width = grid[0].length;


        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 0) {
                    box++;
                }

                if (grid[i][j] == 1) {
                    x = i;
                    y = j;
                }
            }
        }

        total = box;

        boolean[][] visitor = new boolean[grid.length][];

        for (int i = 0; i < visitor.length; i++) {
            visitor[i] = new boolean[grid[0].length];
        }


        visitor[x][y] = true;
        dfs(grid, visitor, x, y, 0);


        return count;
    }


    public void dfs(int[][] grid, boolean[][] visitor, int x, int y, int step) {
        if (step == total) {
            if (x + 1 < height && !visitor[x + 1][y] && grid[x + 1][y] == 2) {
                count++;
                return;
            }

            if (x - 1 >= 0 && !visitor[x - 1][y] && grid[x - 1][y] == 2) {
                count++;
                return;
            }

            if (y + 1 < width && !visitor[x][y + 1] && grid[x][y + 1] == 2) {
                count++;
                return;
            }

            if (y - 1 >= 0 && !visitor[x][y - 1] && grid[x][y - 1] == 2) {
                count++;
                return;
            }
        } else {
            if (x + 1 < height && !visitor[x + 1][y] && grid[x + 1][y] == 0) {
                visitor[x + 1][y] = true;
                dfs(grid, visitor, x + 1, y, step + 1);
                visitor[x + 1][y] = false;
            }

            if (x - 1 >= 0 && !visitor[x - 1][y] && grid[x - 1][y] == 0) {
                visitor[x - 1][y] = true;
                dfs(grid, visitor, x - 1, y, step + 1);
                visitor[x - 1][y] = false;
            }

            if (y + 1 < width && !visitor[x][y + 1] && grid[x][y + 1] == 0) {
                visitor[x][y + 1] = true;
                dfs(grid, visitor, x, y + 1, step + 1);
                visitor[x][y + 1] = false;
            }

            if (y - 1 >= 0 && !visitor[x][y - 1] && grid[x][y - 1] == 0) {
                visitor[x][y - 1] = true;
                dfs(grid, visitor, x, y - 1, step + 1);
                visitor[x][y - 1] = false;
            }
        }
    }
}
